
// 字符串的转换路径问题

#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <unordered_map>
#include <unordered_set>
#include <queue>

using namespace std;

class Solution {
public:
    list<list<string>> findMinPaths(string& start, string to, list<string>& lists) {

        // 1. put start into lists and get Nexts which is a graphy
        lists.emplace_front(start);
        unordered_map <string, list<string> > nexts = getNexts(lists);
        

        // 2. get min distance to every node from nexts graphy
        unordered_map<string, int> distances = getDistances(start, nexts);

        // 3. get all shortest paths to end
        list<list<string>>  res;
        list<string> solution;
        getShortestPaths(start, to, nexts, solution, res, distances);

        return res;

    }

    //多个重载 输出打印结果
    void printAnswer(list<list<string>>& answer) {
        for (auto lists : answer) {
            for (auto str : lists) {
                cout << str << " ";
            }
            cout << endl;
        }
    }

    void printAnswer(unordered_map <string, list<string>>& answer) {
        for (auto pair : answer) {
            cout << pair.first << " ";
            for (auto str : pair.second) {
                cout << str << " ";
            }
            cout << endl;
        }
    }

    void printAnswer(unordered_map<string, int>& answer) {
        for (auto pair : answer) {
            cout << pair.first << " " << pair.second;
            cout << endl;
        }
    }
private:

    // get Nexts
    unordered_map <string, list<string>> getNexts(const list<string>& lists) {
        unordered_map <string, list<string>> res;

        // build string hashTable
        unordered_set <string> listsSet;
        for (auto iter  = lists.begin(); iter != lists.end(); iter++) {
            listsSet.insert(*iter);
        }

        // build string nexts
        for (auto iter  = lists.begin(); iter != lists.end(); iter++) {
            res.insert(make_pair(*iter, getNext(*iter, listsSet)));
        }
        return res;
    }

    // get Next which is one of Nexts
    list<string> getNext(const string& str, const unordered_set<string>& lists) {
        list<string> res;
        string strs(str);
        for (char cur = 'a'; cur <= 'z'; cur++) {
            for (int i = 0; i < strs.size(); i++) {
                if (strs[i] != cur) {
                    char tmp = strs[i];
                    strs[i] = cur;
                    if (lists.count(strs)) {
                        res.emplace_back(strs);
                    }
                    strs[i] = tmp;
                }
            }
        }
        return res;
    }


    // get min distance to every node
    unordered_map<string, int> getDistances(const string& start, const unordered_map<string, list<string>>& nexts) {
        unordered_map <string, int> res;
        res.insert(make_pair(start, 0));
        unordered_set <string> flag;
        flag.insert(start);
        queue <string> que;
        que.push(start);
        while (!que.empty()) {
            string cur = que.front();
            que.pop();
            for (auto str : nexts.at(cur)) {
                if (!flag.count(str)) {
                    res.insert(make_pair(str, res.at(cur) + 1));
                    que.push(str);
                    flag.insert(str);
                }
            }
        }
        return res;
    }

    // get shortest paths

    void getShortestPaths(string& cur, const string& to, 
                                        const unordered_map<string, list<string>>& nexts,
                                        list<string>& solution, list<list<string>>& res,
                                        const unordered_map<string, int>& distances) {
        solution.emplace_back(cur);
        if (to == cur) {
            res.emplace_back(list<string>(solution));
        } else {
            for (auto str : nexts.at(cur)) {
                if (distances.at(str) == distances.at(cur) + 1) {
                    getShortestPaths(str, to, nexts, solution, res, distances);
                }
            }
        }
        solution.pop_back();

        return ;
    }
};

int main() {

    string start = "abc";
    string end = "cab";
    list<string> lists({"abc","cab", "acc", "cbc", "ccc", "cac", "cbb", "aab", "abb"});
    Solution solu;
    list<list<string>> answer = solu.findMinPaths(start, end, lists);

    //unit test 测试getNexts函数是否正确
    //unordered_map <string, list<string>> answer1 = solu.getNexts(lists);

    //测试getDistances函数是否正确
    //unordered_map<string, int> answer = solu.getDistances(start, answer1);
    solu.printAnswer(answer);

    return 0;
    //TODO
}